{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Sum Divisible by P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组和能被 P 整除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>nums</code>，请你移除 <strong>最短</strong>&nbsp;子数组（可以为 <strong>空</strong>），使得剩余元素的 <strong>和</strong>&nbsp;能被 <code>p</code>&nbsp;整除。 <strong>不允许</strong>&nbsp;将整个数组都移除。</p>\n",
    "\n",
    "<p>请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;定义为原数组中连续的一组元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,1,4,2], p = 6\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [6,3,5,2], p = 9\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3], p = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp; 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3], p = 7\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>没有任何方案使得移除子数组后剩余元素的和被 7 整除。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1000000000,1000000000,1000000000], p = 3\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= p &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-sum-divisible-by-p](https://leetcode.cn/problems/make-sum-divisible-by-p/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-sum-divisible-by-p](https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,4,2]\\n6', '[6,3,5,2]\\n9', '[1,2,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        total = sum(nums) % p\n",
    "        prefixsum = [nums[0] % p]\n",
    "        st = {0:-1}\n",
    "        ans = sum(nums)\n",
    "        if total == 0:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for i in range(n):\n",
    "                if i == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    prefixsum.append((prefixsum[i-1]+nums[i]) % p)\n",
    "                if (prefixsum[i] - total) % p in st and i - st[(prefixsum[i] - total) % p] < ans:\n",
    "                    ans = i - st[(prefixsum[i] - total) % p]\n",
    "                st[prefixsum[i]] = i\n",
    "        ans = ans if ans < len(nums) else -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        # 整体余数\n",
    "        mod = sum(nums) % p\n",
    "\n",
    "        if mod == 0:\n",
    "            return 0\n",
    "\n",
    "        # key: 前缀和 % p 的余数\n",
    "        # value: 最晚出现的位置\n",
    "        prefix_sum_map = {0: -1}\n",
    "        ans = float('inf')\n",
    "        cur = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            # 计算 0...i 这部分的余数\n",
    "            cur = (cur + nums[i]) % p\n",
    "            find = cur - mod if cur >= mod else cur + p - mod\n",
    "\n",
    "            if find in prefix_sum_map:\n",
    "                ans = min(ans, i - prefix_sum_map[find])\n",
    "\n",
    "            prefix_sum_map[cur] = i\n",
    "\n",
    "        return ans if ans < len(nums) else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        x = sum(nums) % p\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        y = 0\n",
    "        index ={0:-1}\n",
    "        ans = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            y = (y + v) % p\n",
    "            if (y - x) % p in index:\n",
    "                ans = min(ans, i - index[(y - x) % p])\n",
    "            index[y] = i \n",
    "        return ans if ans < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self,nums:list[int],p:int)->int:\n",
    "\n",
    "        mod = sum(nums)%p\n",
    "\n",
    "        if mod==0:\n",
    "            return 0\n",
    "\n",
    "        prefix_sum_map={0:-1}\n",
    "        ans = float(\"inf\")\n",
    "        cur =0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            cur=(cur+nums[i])%p\n",
    "            find = cur -mod if cur>=mod else cur+p-mod\n",
    "\n",
    "            if find in prefix_sum_map:\n",
    "                ans=min(ans,i-prefix_sum_map[find])\n",
    "\n",
    "            prefix_sum_map[cur]=i\n",
    "\n",
    "\n",
    "        return ans if ans <len(nums) else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        x = sum(nums) % p\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        y = 0\n",
    "        index = {0: -1}\n",
    "        ans = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            y = (y + v) % p\n",
    "            if (y - x) % p in index:\n",
    "                ans = min(ans, i - index[(y - x) % p])\n",
    "            index[y] = i\n",
    "        return ans if ans < len(nums) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        preSum = 0\n",
    "        ans = n = len(nums)\n",
    "        x = sum(nums) % p\n",
    "        # if x == 0: return 0\n",
    "        d = {0: -1}\n",
    "        for i, num in enumerate(nums):\n",
    "            preSum = (preSum + num) % p\n",
    "            d[preSum] = i\n",
    "            j = d.get((preSum - x) % p, -2)\n",
    "            if j > -2 and i - j < ans:\n",
    "                ans = i - j\n",
    "        return ans if ans < n else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        mod = sum(nums) % p\n",
    "        if mod == 0:\n",
    "            return 0\n",
    "        mapping = {0: -1}\n",
    "        sums = 0\n",
    "        result = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            sums = (sums + num) % p\n",
    "            if (sums - mod) % p in mapping:\n",
    "                result = min(result, i - mapping[(sums - mod) % p])\n",
    "            mapping[sums] = i\n",
    "        return result if result < len(nums) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "\n",
    "        total = sum(nums)\n",
    "        if total % p == 0:\n",
    "            return 0\n",
    "            \n",
    "        m = dict()\n",
    "        pre_sum = 0\n",
    "        m[0] = -1\n",
    "        ans = len(nums)\n",
    "        r = total % p \n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            pre_sum = (pre_sum+num) % p\n",
    "            if (pre_sum-r) % p in m:\n",
    "                ans = min(ans, i - m[(pre_sum-r)%p])\n",
    "            m[pre_sum] = i\n",
    "        \n",
    "        return ans if ans < len(nums) else -1\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        # 最短子数组,连续的，不允许 将整个数组都移除\n",
    "        x = sum(nums)\n",
    "        x = x%p\n",
    "        if x == 0:#不移除\n",
    "            return 0\n",
    "        mincnt = n = len(nums)\n",
    "        s = 0\n",
    "        # 不同余数为key,\n",
    "        last = {s: -1}#初始化余数为0的时候，索引为-1\n",
    "        for i,v in enumerate(nums):\n",
    "            s += v\n",
    "            last[s%p] = i\n",
    "            #  pre[i]-pre[j])%p ==x     (pre[i]%p -pre[j]%p) %p = x%p ==>(pre[i] -x)%p = pre[j]%p \n",
    "            if (s-x)%p in last.keys():\n",
    "                mincnt = min(mincnt,i-last[(s-x)%p])\n",
    "        print(last)\n",
    "        if mincnt<n:\n",
    "            return mincnt\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = (presum[i] + nums[i]) % p\n",
    "        # 此段区间mod p == 整个数组 mod p\n",
    "        # (presum[i] - presum[j] + p) % p == target -> presum[j] = (presum[i] - target + p) % p\n",
    "        target = presum[-1]\n",
    "        # print(presum)\n",
    "        if target == 0: return 0\n",
    "        c = Counter()\n",
    "        c[0] = -1\n",
    "        ans = 10**5 + 1\n",
    "        for i in range(n):\n",
    "            pre = (presum[i + 1] - target + p) % p\n",
    "            if pre in c:\n",
    "                if i - c[pre] == n: continue\n",
    "                ans = min(ans, i - c[pre])\n",
    "            c[presum[i + 1]] = i\n",
    "        return ans if ans != 10**5 + 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = (presum[i] + nums[i]) % p\n",
    "        # 此段区间mod p == 整个数组 mod p\n",
    "        # (presum[i] - presum[j] + p) % p == target -> presum[j] = (presum[i] - target + p) % p\n",
    "        target = presum[-1]\n",
    "        if target == 0: return 0\n",
    "        c = Counter()\n",
    "        for i in range(n + 1):\n",
    "            pre = (presum[i] - target + p) % p\n",
    "            if pre in c:\n",
    "                ans = min(ans, i - c[pre])\n",
    "            c[presum[i]] = i\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        # 与题解代码不一样，但是是按题解思考的,双重循环暴力法过不了\n",
    "        # 求余数\n",
    "        target = sum(nums) % p\n",
    "        if target == 0:\n",
    "            return 0\n",
    "        # 求前缀和数组，初始化ans\n",
    "        length = len(nums)\n",
    "        ans = length\n",
    "        for i in range(1, length):\n",
    "            nums[i] += nums[i-1]\n",
    "        # 零个元素时，余数为0，不初始化会出错\n",
    "        yushu = {0:-1}\n",
    "        for i, v in enumerate(nums):\n",
    "            # 目标数为：(v % p− target % p + p) % p，简化为(v - target) % p\n",
    "            if (v - target) % p in yushu:\n",
    "                ans = min(ans, i - yushu[(v - target) % p])\n",
    "            # 更新余数索引字典\n",
    "            yushu[v % p] = i\n",
    "        return ans if ans < len(nums) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            leave = num % p\n",
    "            pre.append((pre[-1]+leave) % p)\n",
    "        if pre[-1] == 0:\n",
    "            return 0\n",
    "        ans = float('inf')\n",
    "        n = len(pre)\n",
    "        index = {}\n",
    "        for i in range(n):\n",
    "            if (pre[i]-pre[-1]+p)%p in index:\n",
    "                ans = min(ans,i-index[(pre[i]-pre[-1]+p)%p])\n",
    "            index[pre[i]] = i\n",
    "        \n",
    "        return ans if ans != n-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        sums, maps = 0, dict()\n",
    "        for x in nums:\n",
    "            sums = (sums + x) % p\n",
    "        ans = 0 if sums == 0 else float('inf')\n",
    "        preSum = [0]\n",
    "        maps[0] = -1\n",
    "        for i in range(len(nums)):\n",
    "            preSum.append((preSum[-1] + nums[i]) % p)\n",
    "        # print(preSum)\n",
    "        for i, x in enumerate(nums):\n",
    "            # print(maps, (preSum[i+1]+p-sums)%p)\n",
    "            if maps.get((preSum[i+1]+p-sums)%p, -2) != -2:\n",
    "                ans = min(ans, i - maps[(preSum[i+1]+p-sums)%p])\n",
    "            maps[preSum[i+1]] = i\n",
    "        return -1 if ans == len(nums) else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            leave = num % p\n",
    "            pre.append((pre[-1]+leave) % p)\n",
    "        if pre[-1] == 0:\n",
    "            return 0\n",
    "        ans = float('inf')\n",
    "        n = len(pre)\n",
    "        index = {}\n",
    "        for i in range(n):\n",
    "            if (pre[i]-pre[-1]+p)%p in index:\n",
    "                ans = min(ans,i-index[(pre[i]-pre[-1]+p)%p])\n",
    "            index[pre[i]] = i\n",
    "        \n",
    "        return ans if ans != n-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        cnt = list(accumulate(nums, initial = 0))\n",
    "        cnt = [x % p for x in cnt]\n",
    "        m = cnt[-1]\n",
    "        if m == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = len(nums)\n",
    "        last = {}\n",
    "        for i, d in enumerate(cnt):\n",
    "            x = (d - m + p) % p\n",
    "            if x in last:\n",
    "                ans = min(ans, i - last[x])\n",
    "            last[d] = i\n",
    "\n",
    "        return ans if ans != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        #模板问题，一样的是前缀和+哈希map\n",
    "        pre_sum=[0];t=0\n",
    "        for num in nums:\n",
    "            t+=num\n",
    "            pre_sum.append(t)\n",
    "        pre_sum=[pre%p for pre in pre_sum]\n",
    "        dct={0:0}\n",
    "        total_sum=pre_sum[-1]\n",
    "        total_sum%=p\n",
    "        #把空数组的情况去掉\n",
    "        min_l=inf\n",
    "        for i in range(len(pre_sum)):\n",
    "            index=dct.get((pre_sum[i]-total_sum)%p,-1)\n",
    "            if index<0:\n",
    "                dct[pre_sum[i]]=i\n",
    "            else:\n",
    "                if index==0 and i==len(pre_sum)-1:\n",
    "                    break\n",
    "                if i-index<min_l:\n",
    "                    min_l=i-index\n",
    "                dct[pre_sum[i]]=i #尽可能地更近\n",
    "        return min_l if min_l!=inf else -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        #模板问题，一样的是前缀和+哈希map\n",
    "        pre_sum=[0];t=0\n",
    "        for num in nums:\n",
    "            t+=num\n",
    "            pre_sum.append(t)\n",
    "        pre_sum=[pre%p for pre in pre_sum]\n",
    "        dct={}\n",
    "        total_sum=pre_sum[-1]\n",
    "        total_sum%=p\n",
    "        #把空数组的情况去掉\n",
    "        if total_sum==0:\n",
    "            return 0\n",
    "        min_l=inf\n",
    "        for i in range(len(pre_sum)):\n",
    "            index=dct.get((pre_sum[i]-total_sum)%p,-1)\n",
    "            if index<0:\n",
    "                dct[pre_sum[i]]=i\n",
    "            else:\n",
    "                if index==0 and i==len(pre_sum)-1:\n",
    "                    break\n",
    "                if i-index<min_l:\n",
    "                    min_l=i-index\n",
    "                dct[pre_sum[i]]=i #尽可能地更近\n",
    "        return min_l if min_l!=inf else -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums, p: int) -> int:\n",
    "        l_len = res = len(nums)\n",
    "        qb = [0] * (l_len + 1)\n",
    "        for index, val in enumerate(nums):\n",
    "            qb[index + 1] = qb[index] + val\n",
    "        mmm = qb[-1] % p\n",
    "        if mmm == 0: return 0\n",
    "        dddd = {0: -1}\n",
    "        for index, val in enumerate(nums):\n",
    "            t = (qb[index + 1] % p - mmm + p) % p\n",
    "            if t in dddd:\n",
    "                res = min(res, index - dddd[t])\n",
    "                if res == 1 and res != l_len:\n",
    "                    return res\n",
    "            dddd[qb[index + 1] % p] = index\n",
    "        if res == l_len: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        res = len(nums)\n",
    "        sum_val = sum(nums)\n",
    "        mod = sum_val % p\n",
    "\n",
    "        if sum_val < p:\n",
    "            return -1\n",
    "\n",
    "        if mod == 0:\n",
    "            return 0\n",
    "\n",
    "        pre = list(itertools.accumulate(nums))\n",
    "\n",
    "        hash_obj = {0: -1}\n",
    "\n",
    "        for i in range(len(pre)):\n",
    "            submod = pre[i] % p\n",
    "            currmod = (submod - mod + p) % p\n",
    "\n",
    "            if currmod in hash_obj:\n",
    "                res = min(res, i - hash_obj[currmod])\n",
    "\n",
    "                if res == 1 and res != len(nums):\n",
    "                    return res\n",
    "\n",
    "            hash_obj[submod] = i\n",
    "\n",
    "        if res == len(nums):\n",
    "            res = -1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if s < p:\n",
    "            return -1\n",
    "        mod = s % p\n",
    "        if not mod:\n",
    "            return 0\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = l = len(nums)\n",
    "        dic = {0:-1}\n",
    "        for i in range(l):\n",
    "            currmod = pre[i] % p\n",
    "            tarmode = (currmod - mod + p)%p\n",
    "            if tarmode in dic:\n",
    "                dis = i - dic.get(tarmode)\n",
    "                ans = min(dis,ans)\n",
    "                if ans == 1 and l != 1:\n",
    "                    return 1\n",
    "            dic[currmod] = i\n",
    "        if ans == l:\n",
    "            return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        presum=list(accumulate(nums,add))#前缀和\n",
    "        hashmap={0:-1}\n",
    "        mod=presum[-1]%p\n",
    "        lenth=len(nums)\n",
    "        res=lenth\n",
    "        if mod==0:\n",
    "            return 0\n",
    "        for i in range(lenth):\n",
    "            curmod=presum[i]%p\n",
    "            tarmod=(curmod-mod+p)%p\n",
    "            if tarmod in hashmap:\n",
    "                dis=i-hashmap[tarmod]\n",
    "                if res > dis :\n",
    "                    res=dis\n",
    "                if res==1 and lenth !=1:\n",
    "                    return 1\n",
    "            hashmap[curmod]=i\n",
    "        if res==lenth:\n",
    "            return -1\n",
    "        return res\n",
    "                         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = list(accumulate(nums, add))\n",
    "        mod = pre[-1] % p\n",
    "        hashT = {0:-1}\n",
    "        if mod == 0: return 0\n",
    "\n",
    "        res = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            curmod = pre[i] % p\n",
    "            tarmod = (curmod - mod + p) % p\n",
    "            if tarmod in hashT:\n",
    "                dis = i - hashT[tarmod]\n",
    "                res = dis if dis < res else res\n",
    "                if res == 1 and len(nums) != 1:\n",
    "                    return 1\n",
    "            hashT[curmod] = i\n",
    "        if res == len(nums):\n",
    "            res = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "\n",
    "        res = sum(nums)%p\n",
    "\n",
    "        if res == 0:\n",
    "            return 0\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = n\n",
    "\n",
    "        pres = {0:-1}\n",
    "\n",
    "        for i in range(1,n):\n",
    "            nums[i] += nums[i-1]\n",
    "            \n",
    "        for i in range(n):\n",
    "            \n",
    "            cur = nums[i] % p\n",
    "            \n",
    "            target = (cur + p - res) % p\n",
    "            \n",
    "            if target in pres:\n",
    "                ans = min(ans, i - pres[target])\n",
    "                \n",
    "            pres[cur] = i\n",
    "\n",
    "        return -1 if ans == n else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = list(accumulate(nums, add))\n",
    "        mod = pre[-1] % p\n",
    "        hashT = {0:-1}\n",
    "        if mod == 0: return 0\n",
    "\n",
    "        res = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            curmod = pre[i] % p\n",
    "            tarmod = (curmod - mod + p) % p\n",
    "            if tarmod in hashT:\n",
    "                dis = i - hashT[tarmod]\n",
    "                res = dis if dis < res else res\n",
    "                if res == 1 and len(nums) != 1:\n",
    "                    return 1\n",
    "            hashT[curmod] = i\n",
    "        if res == len(nums):\n",
    "            res = -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pres = list(accumulate(nums))\n",
    "        n, total = len(nums), pres[-1]\n",
    "        if total % p == 0:\n",
    "            return 0\n",
    "        if total < p:\n",
    "            return -1\n",
    "        m = total % p\n",
    "\n",
    "        ans = n\n",
    "        # 让第一个符合要求的子串能够被计算长度\n",
    "        cache = {0: -1}\n",
    "        for i, pre in enumerate(pres):\n",
    "            cur_mod = pre % p\n",
    "            tar_mod = (cur_mod - m + p) % p\n",
    "            if tar_mod in cache:\n",
    "                ans = min(ans, i - cache[tar_mod])\n",
    "                if ans == 1:\n",
    "                    return 1\n",
    "            cache[cur_mod] = i\n",
    "        return ans if ans != n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        presum = list(accumulate(nums))\n",
    "        extermod = presum[-1] % p\n",
    "        if extermod == 0: return 0\n",
    "        numslen = len(nums)\n",
    "        res = len(nums)\n",
    "        moddict = {}\n",
    "        moddict[0] = -1\n",
    "        for i in range(numslen):\n",
    "            presumx = presum[i]\n",
    "            xmod = presumx % p\n",
    "            findsubmod = (xmod - extermod + p) %p\n",
    "            if findsubmod in moddict:\n",
    "                sublen = moddict[findsubmod]\n",
    "                tempres = i-sublen\n",
    "                res = tempres if res>tempres else res\n",
    "                if res == 1 and len(nums) != 1:\n",
    "                    return 1\n",
    "            moddict[xmod] = i\n",
    "        if res == numslen: return -1\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "#         pre = list(accumulate(nums, add))\n",
    "#         mod = pre[-1] % p\n",
    "#         hashT = {0:-1}\n",
    "#         if mod == 0: return 0\n",
    "\n",
    "#         res = len(nums)\n",
    "#         for i in range(len(nums)):\n",
    "#             curmod = pre[i] % p\n",
    "#             tarmod = (curmod - mod + p) % p\n",
    "#             if tarmod in hashT:\n",
    "#                 dis = i - hashT[tarmod]\n",
    "#                 res = dis if dis < res else res\n",
    "#                 if res == 1 and len(nums) != 1:\n",
    "#                     return 1\n",
    "#             hashT[curmod] = i\n",
    "#         if res == len(nums):\n",
    "#             res = -1\n",
    "#         return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        presum = list(accumulate(nums))\n",
    "        extermod = presum[-1] % p\n",
    "        if extermod == 0: return 0\n",
    "        numslen = len(nums)\n",
    "        res = len(nums)\n",
    "        moddict = {}\n",
    "        moddict[0] = -1\n",
    "        for i in range(numslen):\n",
    "            presumx = presum[i]\n",
    "            xmod = presumx % p\n",
    "            findsubmod = (xmod - extermod + p) %p\n",
    "            if findsubmod in moddict:\n",
    "                sublen = moddict[findsubmod]\n",
    "                tempres = i-sublen\n",
    "                res = tempres if res>tempres else res\n",
    "                # if res == 1 and len(nums) != 1:\n",
    "                #     return 1\n",
    "            moddict[xmod] = i\n",
    "        if res == numslen: return -1\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "#         pre = list(accumulate(nums, add))\n",
    "#         mod = pre[-1] % p\n",
    "#         hashT = {0:-1}\n",
    "#         if mod == 0: return 0\n",
    "\n",
    "#         res = len(nums)\n",
    "#         for i in range(len(nums)):\n",
    "#             curmod = pre[i] % p\n",
    "#             tarmod = (curmod - mod + p) % p\n",
    "#             if tarmod in hashT:\n",
    "#                 dis = i - hashT[tarmod]\n",
    "#                 res = dis if dis < res else res\n",
    "#                 if res == 1 and len(nums) != 1:\n",
    "#                     return 1\n",
    "#             hashT[curmod] = i\n",
    "#         if res == len(nums):\n",
    "#             res = -1\n",
    "#         return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        r = sum(nums) % p\n",
    "        \n",
    "        prefix = [0] + list(accumulate(nums))\n",
    "\n",
    "        # 哈希表：key为前缀和对p的余数，值为最大下标\n",
    "        hashmap = {}\n",
    "\n",
    "        n = len(prefix)\n",
    "        \n",
    "        ans = n - 1\n",
    "        for i in range(n):\n",
    "            right = prefix[i] % p \n",
    "            hashmap[right] = i\n",
    "\n",
    "            left = (right - r) % p \n",
    "            \n",
    "            if left in hashmap:\n",
    "                ans = min(ans, i - hashmap[left])\n",
    "\n",
    "        return ans if ans != n - 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        ans = len(nums)\n",
    "        k = sum(nums)%p\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        last = {0: '-1'}\n",
    "        cur = 0\n",
    "        for i in range(ans):\n",
    "            cur += nums[i]\n",
    "            cur %= p\n",
    "            target = (cur - k + p) % p\n",
    "            if target in last:\n",
    "                ans = min(ans, i - int(last[target]))\n",
    "            last[cur] = str(i)\n",
    "        return ans if ans != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        sum1 = sum(nums)%p\n",
    "        if sum1 == 0:\n",
    "            return 0\n",
    "        if sum(nums) < p:\n",
    "            return -1\n",
    "        \n",
    "        nums = [0] + nums\n",
    "        len1 = len(nums)\n",
    "        res,dic = len1,{0:0}\n",
    "        for i in range(1,len1):\n",
    "            nums[i] = (nums[i] + nums[i-1])%p\n",
    "            target = (nums[i]+p-sum1)%p\n",
    "            if target in dic:\n",
    "                res = min(res,i-dic[target])  \n",
    "            dic[nums[i]%p] = i\n",
    "        #print(sum1,nums)\n",
    "        return res if res < len1 - 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        k = sum(nums) % p\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        s = [0]\n",
    "        for num in nums:\n",
    "            s.append((s[-1] + num)%p)\n",
    "        ans = len(nums)\n",
    "        d = {} # 前缀\n",
    "        for i, v in enumerate(s):\n",
    "            \n",
    "            j = d.get((v-k)%p, -len(nums))\n",
    "            ans = min(i-j, ans)\n",
    "            d[v%p] = i \n",
    "            \n",
    "        return ans if ans != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        su = sum(nums)\n",
    "        nums = list(map(lambda x: x % p, nums))\n",
    "        s = su // p\n",
    "        if not s:\n",
    "            return -1\n",
    "        res = len(nums)\n",
    "        if su % p == 0:\n",
    "            return 0\n",
    "        left = su % p\n",
    "        d = {}\n",
    "        d[0]=-1\n",
    "        add =0\n",
    "        for i in range(len(nums)):\n",
    "            add+=nums[i]\n",
    "            add%=p\n",
    "            key = (add-left + p) %p\n",
    "            if key in d:\n",
    "                res = min(res,i-d[key])\n",
    "            d[add]=i\n",
    "        return -1 if res >=len(nums) else res    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        k = sum(nums) % p\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        # nums = [num%p for num in nums]\n",
    "        s = [0]\n",
    "        for num in nums:\n",
    "            s.append((s[-1] + num)%p)\n",
    "        ans = len(nums)\n",
    "        # d = {0: -1}\n",
    "        d = {}\n",
    "        for i, v in enumerate(s):\n",
    "            d[v%p] = i \n",
    "            j = d.get((v-k)%p, -len(nums))\n",
    "            ans = min(i-j, ans)\n",
    "            \n",
    "        return ans if ans != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        preSum = [0]\n",
    "        for i in range(n):\n",
    "            preSum.append((preSum[i]+nums[i])%p)\n",
    "        k = preSum[n]\n",
    "        if k == 0: return 0\n",
    "        ans = n\n",
    "        # 用哈希表记录前面最靠右的一个被p除余k的idx（数组不行 1e9的数组太大了）\n",
    "        rightMost = {0: -1}  # 数组为空时被p除余0\n",
    "        for i in range(n):\n",
    "            cur = preSum[i+1] % p\n",
    "            bef = (cur - k + p) % p\n",
    "            if bef in rightMost:\n",
    "                ans = min(ans, i - rightMost[bef])  # 删除[rightMost[bef]+1,i]部分\n",
    "            if cur in rightMost:    \n",
    "                rightMost[cur] = max(rightMost[cur], i)\n",
    "            else:\n",
    "                rightMost[cur] = i\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        nums = [a % p for a in nums]\n",
    "        s = sum(nums) % p\n",
    "        if s == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = inf\n",
    "        d = {0: -1}\n",
    "        t = 0\n",
    "        for i, a in enumerate(nums):\n",
    "            t += a\n",
    "            if (t - s) % p in d:\n",
    "                ans = min(ans, i - d[(t - s) % p])\n",
    "            d[t % p] = i\n",
    "        \n",
    "        return ans if ans != len(nums) else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        k = sum(nums) % p\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        nums = [num%p for num in nums]\n",
    "        s = [0]\n",
    "        for num in nums:\n",
    "            s.append((s[-1] + num)%p)\n",
    "        # ans = len(nums)\n",
    "        # d = {0: -1}\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     d[v%p] = i \n",
    "        #     j = d.get((k-v)%p, -len(nums))\n",
    "        #     # if abs(k-v)%p in d:\n",
    "        #     ans = min(i-j, ans)\n",
    "            \n",
    "        # print(ans)\n",
    "        # print(nums)\n",
    "        # return ans if ans != len(nums) else -1\n",
    "\n",
    "        ans = len(nums)\n",
    "        d = {0: -1}\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s += v\n",
    "            d[s%p] = i \n",
    "            j = d.get((s-k)%p, -len(nums))\n",
    "            ans = min(i-j, ans)\n",
    "            \n",
    "        return ans if ans != len(nums) else -1\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        dic = {}\n",
    "        s = sum(nums)\n",
    "        t = s%p\n",
    "        print(t)\n",
    "        if t == 0:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0: dp[i] = nums[0]\n",
    "            dp[i] = dp[i-1]+nums[i]\n",
    "            dp[i] %= p\n",
    "            if nums[i] == t:\n",
    "                return 1\n",
    "            if dp[i] in dic:\n",
    "                dic[dp[i]].append(i)\n",
    "            else:\n",
    "                dic[dp[i]] = [i]\n",
    "        print(dp)\n",
    "        ans = 10**10\n",
    "        for i in range(0,len(nums)):\n",
    "            if i < len(nums)-1 and dp[i] == t:\n",
    "                ans = min(ans,i+1)\n",
    "            u = (dp[i]+t)%p\n",
    "            if u in dic:\n",
    "                for j in dic[u]:\n",
    "                    if i > j:\n",
    "                        continue\n",
    "                    ans = min(ans, abs(i-j))\n",
    "        if ans == 10**10:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        # nums = [i%p for i in nums]\n",
    "        # print(nums)\n",
    "        pre = list(accumulate(nums,initial=0))\n",
    "        # print(pre)\n",
    "        pre = [i%p for i in pre]\n",
    "        # print(pre)\n",
    "        target = pre[-1] % p\n",
    "        # print(target)\n",
    "        if target == 0:return 0\n",
    "        ans = n = len(nums)\n",
    "        dic = defaultdict(int)\n",
    "        for i, v in enumerate(pre):\n",
    "            dic[v % p] = i\n",
    "            j = dic.get((v - target) % p, -n)  # 如果不存在，-n 可以保证 i-j >= n\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        d = dict()  #   记录前N项和的位置\n",
    "                \n",
    "        cur = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            cur += v\n",
    "            c2 = cur % p\n",
    "            if c2 not in d:\n",
    "                d[c2] = []\n",
    "            d[c2].append(i)\n",
    "        \n",
    "        l = cur % p\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        if cur < p:\n",
    "            return -1\n",
    "        \n",
    "        #   整个数列的余数是l，那就需要找一个最短的子序列，使得它的余数为l。\n",
    "        \n",
    "        rtv = len(nums)\n",
    "        cur = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            cur += v\n",
    "            c2 = cur % p\n",
    "            tar = c2 - l\n",
    "            if tar < 0:\n",
    "                tar += p\n",
    "            \n",
    "            if tar == 0:\n",
    "                rtv = min(rtv, i+1)\n",
    "            if tar in d:\n",
    "                pos = bisect.bisect_left(d[tar], i)\n",
    "                if pos == len(d[tar]) or d[tar][pos] > i:\n",
    "                    pos = pos -1\n",
    "                pos = d[tar][pos]\n",
    "                if pos <= i:\n",
    "                    rtv = min(rtv, i-pos)\n",
    "        if rtv == len(nums):\n",
    "            rtv = -1\n",
    "        return rtv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        tmp = {0:[-1]}\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s = (s + num) % p\n",
    "        if s == 0:\n",
    "            return 0\n",
    "        t = 0\n",
    "        minNum = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            t = (t + num) % p\n",
    "            x = (p - (p+s-t)%p)%p\n",
    "            if x in tmp:       \n",
    "                if minNum > i-tmp[x][-1]:\n",
    "                    minNum = i-tmp[x][-1]\n",
    "            if t % p in tmp:\n",
    "                tmp[t % p].append(i)\n",
    "            else:\n",
    "                tmp[t % p] = [i]\n",
    " \n",
    "        if minNum == len(nums):\n",
    "            return -1\n",
    "        return minNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        preSum, preSum_mod = [0 for _ in range(n+1)], [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            preSum[i] = preSum[i-1]+nums[i-1]\n",
    "            preSum_mod[i] = preSum[i]%p\n",
    "        if preSum[-1]%p==0: return 0\n",
    "        elif preSum[-1] < p: return -1\n",
    "        \n",
    "        total_mod = preSum[-1]%p\n",
    "        hashmap, ans = {0:0}, n\n",
    "        for i in range(1, n+1):\n",
    "            if preSum_mod[i] >= total_mod and preSum_mod[i] - total_mod in hashmap:\n",
    "                ans = min(ans, i-hashmap[preSum_mod[i]-total_mod])\n",
    "            elif preSum_mod[i] < total_mod and preSum_mod[i] + p-total_mod in hashmap:\n",
    "                ans = min(ans, i-hashmap[preSum_mod[i]+p-total_mod])\n",
    "            hashmap[preSum_mod[i]] = i\n",
    "        return ans if ans != n else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p:int) -> int:\n",
    "        nums = [num%p for num in nums]\n",
    "        n = len(nums)\n",
    "        pre_sum = [0 for _ in range(n)]\n",
    "        summ = 0\n",
    "        target = sum(nums)%p\n",
    "        #print(target)\n",
    "        if target == 0:\n",
    "            return 0\n",
    "\n",
    "        dicc = {}\n",
    "        dicc[0] = -1\n",
    "        minn = n\n",
    "        for i in range(n):\n",
    "            summ = (summ+nums[i])% p \n",
    "            pre_sum[i] = summ\n",
    "            wanted = summ - target\n",
    "            wanted = wanted + (p if wanted<0 else 0)\n",
    "            #print(i,summ,wanted)\n",
    "            if wanted in dicc:\n",
    "                if i-dicc[wanted] < minn:\n",
    "                    minn = i-dicc[wanted]\n",
    "            dicc[summ] = i\n",
    "\n",
    "\n",
    "        return (-1 if minn==n else minn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        # 首先得到需要的数组的取余数\n",
    "        s = sum(nums)\n",
    "        mod = s % p\n",
    "        if mod == 0:\n",
    "            return 0\n",
    "        if s < p:\n",
    "            return -1\n",
    "        # 考虑到前缀和求数组的和是个减法，如果第一个前缀和mod是2，后面一个前缀和mod是3，那么相减之后的mod就是1\n",
    "        # 然后对于每一个前缀和，保存在哈希表中，比如需要的mod是1，p是11，现在算出来是6，那哈希表中就应该存后面那个前缀和是多少才能满足\n",
    "        # 后面的前缀和应该是7，也就是mod + now，如果超过p，再取余p，比如mod是10，p是11，现在算出来是6，那就是(6 + 10) % 11 = 5\n",
    "        pre = [0]\n",
    "        n = len(nums)\n",
    "        index = {mod: 0}  # 初始时，如果有一个前缀和是mod，那它可以减0\n",
    "        res = n\n",
    "        for i in range(1, n + 1):\n",
    "            pre.append(pre[-1] + nums[i - 1])\n",
    "            # 看现在的mod能不能满足\n",
    "            now = pre[i] % p\n",
    "            if now in index:\n",
    "                res = min(i - index[now], res)\n",
    "            index[(mod + now) % p] = i\n",
    "        return res if res < n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = [nums[0]]\n",
    "        s = sum(nums)\n",
    "        if s % p == 0:\n",
    "            return 0\n",
    "        if s < p:\n",
    "            return -1\n",
    "        s = s % p\n",
    "        print(s)\n",
    "        d = {}\n",
    "        d[0] = 0\n",
    "        d[nums[0] % p] = 1\n",
    "        \n",
    "        # d[0] = \n",
    "        r = 1000000\n",
    "        for i in range(1, len(nums)):\n",
    "            pre.append(pre[i-1] + nums[i])\n",
    "            now = pre[-1] % p\n",
    "            if i == (len(nums)-1):\n",
    "                print(\"pre\", pre[-1], \"now\", now)\n",
    "            # if now == s:\n",
    "            #     r = min(r, i+1)\n",
    "            if now >= s:\n",
    "                if d.get(now-s, -1) >= 0:\n",
    "                    r = min(r, i+1 - d[now-s])\n",
    "            else:\n",
    "                if d.get(now + p -s, -1) >= 0:\n",
    "                    r = min(r, i+1 - d[now + p -s]) \n",
    "            d[now] = i+1\n",
    "        if r == len(nums) and s != 0:\n",
    "            return -1\n",
    "        return r if r != 1000000 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        nums = [n % p for n in nums]\n",
    "        # 转化：找到一个最短子数组，使得数组和 % p == m\n",
    "        m = sum(nums) % p\n",
    "        if m == 0: return 0\n",
    "\n",
    "        dic = {0: -1}\n",
    "        cur, ans = 0, len(nums)\n",
    "        for i, n in enumerate(nums):\n",
    "            cur = (cur + n) % p\n",
    "            target = (cur - m) % p\n",
    "            if (j := dic.get(target)) is not None and i - j < ans:\n",
    "                ans = i - j\n",
    "            dic[cur] = i\n",
    "        \n",
    "        return ans if ans < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        prefix= [0]\n",
    "        d = {0:-1}\n",
    "        s = sum(nums)\n",
    "        x = s % p \n",
    "        if x == 0: return 0\n",
    "        ans = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix.append(num + prefix[-1])\n",
    "            d[prefix[-1]%p] = i \n",
    "            # print(i, prefix[-1], prefix[-1]%p, (prefix[-1]-x+p)%p)\n",
    "            if d.get((prefix[-1]-x+p)%p, None) is not None:\n",
    "                ans = min(ans, i-d[(prefix[-1]-x+p)%p])\n",
    "\n",
    "        return ans if ans < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = sum(nums)\n",
    "        target = s % p\n",
    "        if target == 0:return 0\n",
    "        for idx,i in enumerate(nums):\n",
    "            nums[idx] = i % p\n",
    "        prefix = [0] * (len(nums)+1)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        for idx,i in enumerate(prefix):\n",
    "            prefix[idx] = i % p\n",
    "        print(target)\n",
    "        print(prefix)\n",
    "        D = defaultdict(int)\n",
    "        res = inf\n",
    "        for idx,i in enumerate(prefix):\n",
    "            D[(i+target)%p] = idx\n",
    "            if i in D:res = min(res,idx-D[i])\n",
    "        return res if res != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        nums = [n % p for n in nums]\n",
    "        m = sum(nums) % p\n",
    "        if m == 0: return 0\n",
    "\n",
    "        dic = {0: -1}\n",
    "        cur, ans = 0, len(nums)\n",
    "        for i, n in enumerate(nums):\n",
    "            cur = (cur + n) % p\n",
    "            target = (cur - m) % p\n",
    "            if (j := dic.get(target)) is not None and i - j < ans:\n",
    "                ans = i - j\n",
    "            dic[cur] = i\n",
    "        \n",
    "        return ans if ans < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0\n",
    "\n",
    "        record = {}\n",
    "        ans = n = len(nums)\n",
    "        for i, v in enumerate(s):\n",
    "            record[v % p] = i\n",
    "            j = record.get((v - s[-1]) % p, -n)\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0  # 移除空子数组（这行可以不要）\n",
    "\n",
    "        ans = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(s):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v - x) % p, -n)  # 如果不存在，-n 可以保证 i-j >= n\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        N = len(nums)\n",
    "        xsum = sum(nums)\n",
    "        if xsum % p == 0:\n",
    "            return 0\n",
    "        xsums = list(accumulate(nums, initial=0))\n",
    "        xsum2i = {}\n",
    "        ans = N\n",
    "        for j in range(N+1):\n",
    "            xsum2i[xsums[j] % p] = j\n",
    "            t = (xsums[j] - xsum) % p\n",
    "            if t in xsum2i:\n",
    "                i = xsum2i[t]\n",
    "                ans = min(ans, j-i)\n",
    "        return ans if ans < N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0 \n",
    "\n",
    "        ans = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(s):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v - x) % p, -n)\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # 子数组问题处理 使用前缀和\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0\n",
    "        ans = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(s):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v - x) % p, -n)\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        st = defaultdict(int)\n",
    "        k = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] %= p\n",
    "            k = (k + nums[i])%p\n",
    "        prefix = list(accumulate(nums, initial= 0))\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        #print(prefix)\n",
    "        ans = n + 1\n",
    "        st[0] = -1\n",
    "        for i in range(n):\n",
    "            #print(i, prefix[i + 1] - k , st)\n",
    "            if (prefix[i + 1] - k + p)%p in st:\n",
    "                ans = min(ans, i - st[(prefix[i + 1]%p - k + p)%p])\n",
    "            st[prefix[i + 1]%p] = i\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        tot = sum(nums)\n",
    "        if tot % p == 0: return 0\n",
    "        x = tot % p\n",
    "        n = len(nums)\n",
    "        s = [0] *(n + 1)\n",
    "        for i in range(1, n + 1): \n",
    "            s[i] = s[i - 1] + nums[i - 1] \n",
    "        D = defaultdict(int) \n",
    "        D[0] = 0 \n",
    "        res = inf\n",
    "        for i in range(1, n + 1): \n",
    "            c = ((s[i] - x) % p + p) % p\n",
    "            if c in D: res = min(res, i - D[c])\n",
    "            D[s[i] % p] = i\n",
    "        return res if res != inf and res != n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        sumv = sum(nums)\n",
    "        if sumv % p == 0:\n",
    "            return 0\n",
    "        # P[r+1] - P[l]  = cur\n",
    "        # (sumv - (P[r+1] - P[l]))% p  = 0\n",
    "        P = [0]\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        ans = n\n",
    "        for r, v in enumerate(nums):\n",
    "            P.append(P[-1] + v)\n",
    "            if (P[-1] - sumv) % p in aux:\n",
    "                ans = min(ans, r + 1 - aux[(P[-1] - sumv) % p])\n",
    "            aux[P[-1] % p] = r + 1\n",
    "        return ans if ans != n else -1\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pres=[0]+list(accumulate(nums))\n",
    "        if pres[-1]%p==0:return 0\n",
    "        target=pres[-1]%p\n",
    "        n=len(nums)\n",
    "        ans=n\n",
    "        mem={}\n",
    "        for i,x in enumerate(pres):\n",
    "            if (p+x-target)%p in mem:\n",
    "                ans=min(ans,i-mem[(p+x-target)%p])\n",
    "            mem[x%p]=i\n",
    "      \n",
    "        return -1 if ans==n else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        target = sum(nums) % p\n",
    "        if target == 0:\n",
    "            return 0\n",
    "        tmp = 0\n",
    "        kk = {0:-1}\n",
    "        ss = set()\n",
    "        ss.add(0)\n",
    "        ans = len(nums)\n",
    "        for i,num in enumerate(nums):\n",
    "            tmp += num\n",
    "            tmp = tmp % p\n",
    "            tmptarget = (tmp - target + p) % p\n",
    "            if tmptarget in ss:\n",
    "                ans = min(ans, i - kk[tmptarget])\n",
    "            ss.add(tmp)\n",
    "            kk[tmp] = i\n",
    "        if ans == len(nums):\n",
    "            return -1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        total = sum(nums)\n",
    "        target_mode = total%p\n",
    "        if target_mode==0:\n",
    "            return 0\n",
    "        \n",
    "        \n",
    "        pre_sum = [nums[0]]\n",
    "        for n in nums[1:]:\n",
    "            pre_sum.append(pre_sum[-1]+n)\n",
    "            \n",
    "        map={0:-1}\n",
    "        min_sub = len(nums)\n",
    "        for i,v in enumerate(pre_sum):\n",
    "            target = (v-target_mode)%p\n",
    "            if target in map:\n",
    "                min_sub = min(min_sub,i-map[target])\n",
    "            \n",
    "            map[v%p]=i \n",
    "        # print(min_sub)\n",
    "        # print(pre_mode)\n",
    "        # print(map)\n",
    "        return min_sub if min_sub<len(nums) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums))\n",
    "        s = [0] + s # 很重要！\n",
    "        x = s[-1] % p # 目标和\n",
    "\n",
    "        if x == 0: return 0\n",
    "        # s[i] - s[j] = 目标\n",
    "        l = {}\n",
    "        ans = n\n",
    "        for i, v in enumerate(s):\n",
    "            l[v % p] = i\n",
    "            j = l.get((s[i] - x) % p, -n)\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        ss = sum(nums)\n",
    "        if ss < p: return -1\n",
    "        x1 = ss % p\n",
    "        x2 = ss % p - p\n",
    "        if not x1: return 0\n",
    "        nums = [num%p for num in nums]\n",
    "        a = list(accumulate(nums,initial=0))\n",
    "        a = [aa%p for aa in a]\n",
    "        d = {}\n",
    "        r = inf\n",
    "        #print(a,x1,x2)\n",
    "        for i,v in enumerate(a):\n",
    "            if v-x1 in d:\n",
    "                r = min(r,i-d[v-x1])\n",
    "            elif v-x2 in d:\n",
    "                r = min(r,i-d[v-x2])\n",
    "            d[v] = i\n",
    "        return r if r<len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre_sum = [0] + list(itertools.accumulate(nums))\n",
    "        x = pre_sum[-1] % p\n",
    "        if not x:\n",
    "            return 0  # 移除空子数组（这行可以不要）\n",
    "        ans = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(pre_sum):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v - x) % p, -n)  # 如果不存在，-n 可以保证 i-j >= n\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        need_remove = sum(nums) % p \n",
    "        if need_remove == 0: return 0\n",
    "        prefix = list(accumulate(nums, initial = 0))\n",
    "        res = len(nums)\n",
    "        hash_ = {0:0}\n",
    "        for i, num in enumerate(prefix[1:], 1):\n",
    "            if (num - need_remove) % p in hash_:\n",
    "                res = min(res, i - hash_[(num - need_remove) % p])\n",
    "            hash_[num % p] = i \n",
    "        return res if res < len(nums) else -1\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        need_remove = sum(nums) % p \n",
    "        if need_remove == 0: return 0\n",
    "        \n",
    "        prefix = [0]\n",
    "        for num in nums:\n",
    "            prefix.append(num + prefix[-1])\n",
    "        \n",
    "        res = len(nums)\n",
    "        hash_ = {0:0}\n",
    "        for i, num in enumerate(prefix[1:], 1):\n",
    "            hash_[num % p] = i \n",
    "            j = hash_.get((num - need_remove) % p, -len(nums))\n",
    "            res = min(res, i - j)\n",
    "        return res if res < len(nums) else -1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0  # 移除空子数组（这行可以不要）\n",
    "\n",
    "        ans = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(s):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v - x) % p, -n)  # 如果不存在，-n 可以保证 i-j >= n\n",
    "            ans = min(ans, i - j)\n",
    "        return ans if ans < n else -1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        sum_all = sum(nums)\n",
    "        if sum_all%p==0:\n",
    "            return 0\n",
    "        if sum_all < p:\n",
    "            return -1\n",
    "        y = sum_all%p\n",
    "        d = {}\n",
    "        sum_list = []\n",
    "        sum_ = 0\n",
    "        res = -1\n",
    "        for num in nums:\n",
    "            sum_ += num\n",
    "            sum_list.append(sum_)\n",
    "        tmp = 0\n",
    "        d[0] = -1\n",
    "        for i in range(len(nums)):\n",
    "            tmp += nums[i]\n",
    "            t = tmp%p\n",
    "            his = (t-y) if t>=y else (t+p-y)\n",
    "            if his in d:\n",
    "                res = min(res,i-d[his]) if res!=-1 else (i-d[his])\n",
    "            d[t] = i\n",
    "        return res if res<len(nums) else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        arr1=[0]*(n:=len(nums)+1)\n",
    "        res=len(nums)\n",
    "        dic1={}\n",
    "        dic1[0]=0\n",
    "        s=sum(nums)\n",
    "        x=s % p\n",
    "        if s % p==0:return 0\n",
    "        for i in range(n-1):\n",
    "            arr1[i+1]=arr1[i]+nums[i]\n",
    "            if (arr1[i+1] % p -x+p)  % p in dic1:\n",
    "                res=min(res,i+1-dic1[  (arr1[i+1] % p -x + p)  % p])\n",
    "            dic1[arr1[i + 1] % p] = i+1\n",
    "        return res if res!=len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        x = s[-1] % p\n",
    "        if x == 0: return 0\n",
    "\n",
    "        res = n = len(nums)\n",
    "        last = {}\n",
    "        for i, v in enumerate(s):\n",
    "            last[v % p] = i\n",
    "            j = last.get((v-x) % p, -n)\n",
    "            res = min(res, i-j)\n",
    "\n",
    "        return res if res < n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre =[0]\n",
    "        for num in nums:\n",
    "            pre.append((pre[-1]+num))\n",
    "        smallest =-1\n",
    "        last ={}\n",
    "\n",
    "        amount =sum(nums)%p\n",
    "        if amount==0:\n",
    "            return 0\n",
    "        # print(target,pre)\n",
    "        for i,v in enumerate(pre):\n",
    "            reminder = (v-amount)%p\n",
    "            last[v%p]=i\n",
    "            last_id =last.get(reminder,-len(nums))\n",
    "            \n",
    "            # if last_id>=0:\n",
    "                # print(last_id)\n",
    "            if smallest==-1 or i-last_id <smallest:\n",
    "                smallest = i-last_id\n",
    "            \n",
    "\n",
    "        return smallest if smallest!=len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubarray(self, nums: List[int], p: int) -> int:\n",
    "        pre = list(accumulate(nums, add))\n",
    "        mod = pre[-1] % p\n",
    "        hashT = {0:-1}\n",
    "        if mod == 0: return 0\n",
    "\n",
    "        res = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            curmod = pre[i] % p\n",
    "            tarmod = (curmod - mod + p) % p\n",
    "            if tarmod in hashT:\n",
    "                dis = i - hashT[tarmod]\n",
    "                res = dis if dis < res else res\n",
    "                if res == 1 and len(nums) != 1:\n",
    "                    return 1\n",
    "            hashT[curmod] = i\n",
    "        if res == len(nums):\n",
    "            res = -1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
